[GNN] An Introduction to Graph Neural Network(GNN) For Analysing Structured Data

ref

https://towardsdatascience.com/an-introduction-to-graph-neural-network-gnn-for-analysing-structured-data-afce79f4cfdc

GNN

- GNN개념

1. Recurrent Graph Neural Network (순환 그래프 신경망)
2. Spatial Convolutional Network (공간 컨볼루션 네트워크)
3. Spectral Convolutional Network (스펙트럼 컨볼루션 네트워크)

- GNN 분류

• 노드 분류: 그래프의 모든 노드에 대한 노드 임베딩 예측
• 링크 예측: 그래프에서 개체 간의 관계를 이해하고 두 개체 사이에 연결이 있는지 예측
• 그래프 분류: 전체 그래프를 다양한 카테고리로 분류

- GNN 사례

• 자연어 처리(NLP): 단어나 문서의 내부 관계 활용하여 카테고리 예측

• 컴퓨터 비전(Computer Vision)

RecGNN

Let (X,d) be a complete metric space.

Let (T:X→X) be a contraction mapping.

Then T has a unique fixed point (x∗) and for any x∈X the sequence T_n(x) for n→∞ converges to (x∗).

This means if I apply the mapping T on x for k times, x^k should be almost equal to x^(k-1)

• \(l_n\) 현재 노드의 특징

• \(l_{co}\) 노드의 에지

• \(x_{ne}\) 인접 노드의 상태

• \(l_{ne}\) 인접 노드의 특징(노드 레이블)

이웃 노드의 정보를 기반으로 노드 상태 업데이트

- 출력 함수

Spatial Convolutional Network

• CNN과 유사(이미지에서 컨볼루션은 매개변수화된 크기와 학습이 가능한 가중치를 가진 필터로 지정된 중심 픽셀 주변의 인접 픽셀을 합산)

• 공간 컨볼루션 네트워크는 인접 노드의 특징을 중심 노드에 합산하여 동일한 아이디어 채택

Spectral Convolutional Network

• 체비셰프 다항식 근사법

• 2계층 신경망 구조

• \(\hat A\): 그래프 인접 행렬 A의 사전 처리된 라플라스 행렬

- 예시

• 인접행렬의 대각선은 모든 노드에 대한self-loop를 하기 위해 1로 변경

• 특정 집계를 수행할 때 모든 노든 자체의 특징 포함

- 그래프 신경망

• 메시지 전달 함수

• 노드 업데이트 함수

• 판독 함수가 있는 메시지 전달 신경망

References

• F.Scarselli, M.Gori, “The graph neural network model,” IEEE Transactions on Neural Networks, 2009

• T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. of ICLR, 2017.

• Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, “A Comprehensive Survey on Graph Neural Networks”, arXiv:1901.00596

• D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, vol. 2, 2017

• J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018

• X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018